// Problem: 
// Contest: 
// URL: 
// Memory Limit: 
// Time Limit: 
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
//inline int ck(int x)
//{
//	if(x==0)return 1;
//	int sum=1;
//	for(int i=1;i<=x;i++)sum*=i;
//	return sum;
//}
vector<vector<int>> c(2002,vector<int>(2002));
auto ans=c;
//int C(int m,int n)
//{
//	int ret=1;
//	for(int i=1;i<=m;i++)
//	{
//		ret=ret*n/i;
//		n--;
//	}
//	return ret;
//	//return ck(n)/(ck(m)*ck(n-m));
//}
int T=1,k;
inline void build()
{
	c[0][0]=1;
	c[1][0]=c[1][1]=1;
	for(int i=2;i<=2000;i++)
	{
		c[i][0]=1;
		for(int j=1;j<=i;j++)
		{
			c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;
			ans[i][j]=ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1];
			if(!c[i][j])ans[i][j]++;
		}
		ans[i][i+1]=ans[i][i];
	}
}
signed main()
{
	cin>>T>>k;
	build();
	while(T--)
	{
		int n,m;
		cin>>n>>m;
//		for(int i=1;i<=n;i++)
//		{
//			for(int j=1;j<=min(i,m);j++)
//			{
//				if(C(j,i)%k==0)ans++;
//			}
//		}
		if(m>n)cout<<ans[n][n]<<endl;
		else cout<<ans[n][m]<<endl;
	}
	return 0;
}
